# 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
#  返回 滑动窗口中的最大值 。
#
#  示例 1：
# 输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
# 输出：[3,3,5,5,6,7]
# 解释：
# 滑动窗口的位置                最大值
# ---------------               -----
# [1  3  -1] -3  5  3  6  7       3
#  1 [3  -1  -3] 5  3  6  7       3
#  1  3 [-1  -3  5] 3  6  7       5
#  1  3  -1 [-3  5  3] 6  7       5
#  1  3  -1  -3 [5  3  6] 7       6
#  1  3  -1  -3  5 [3  6  7]      7
#
#  示例 2：
# 输入：nums = [1], k = 1
# 输出：[1]
import heapq
from typing import List


class Solution:


    def maxSlidingWindow4(self, nums: List[int], k: int) -> List[int]:
        """
        单调队列写法二
        使用一个队列存储所有还没有被移除的下标。在队列中，这些下标按照从小到大的顺序被存储，并且它们在数组 nums 中对应的值是严格单调递减的
        即要满足 nums[deque[i]] > nums[deque[i + 1]]

        如果当前的滑动窗口中有两个下标 i 和 j，其中 i 在 j 的左侧（i < j），并且 i 对应的元素不大于 j 对应的元素（nums[i] <= nums[j]）
        则当滑动窗口向右移动时，只要 i 还在窗口中，那么 j 一定也还在窗口中，这是 i 在 j 的左侧所保证的。
            由于 nums[j] 的存在，nums[i] 一定不会是滑动窗口中的最大值了，就可以将 nums[i] 永久地移除

        :param nums:
        :param k:
        :return:
        """
        import collections
        numLen, dq, res = len(nums), collections.deque(), []

        for i in range(numLen):
            while dq and nums[i] >= nums[dq[-1]]:  # 保证一定有nums[dq[i]] > nums[dq[i + 1]]
                dq.pop()
            dq.append(i)
            while dq[0] <= i - k:  # 当前的最大值索引比当前窗口的左边界小，也需要移除
                dq.popleft()
            if i >= k - 1:
                res.append(nums[dq[0]])
        return res

    def maxSlidingWindow3(self, nums: List[int], k: int) -> List[int]:
        """
        单调队列
        使用一个队列存储所有还没有被移除的下标。在队列中，这些下标按照从小到大的顺序被存储，并且它们在数组 nums 中对应的值是严格单调递减的
        即要满足 nums[deque[i]] > nums[deque[i + 1]]

        如果当前的滑动窗口中有两个下标 i 和 j，其中 i 在 j 的左侧（i < j），并且 i 对应的元素不大于 j 对应的元素（nums[i] <= nums[j]）
        则当滑动窗口向右移动时，只要 i 还在窗口中，那么 j 一定也还在窗口中，这是 i 在 j 的左侧所保证的。
            由于 nums[j] 的存在，nums[i] 一定不会是滑动窗口中的最大值了，就可以将 nums[i] 永久地移除

        :param nums:
        :param k:
        :return:
        """
        import collections
        numLen, dq = len(nums), collections.deque()
        for i in range(k):  # 初始化单调队列
            while dq and nums[i] >= nums[dq[-1]]:
                dq.pop()
            dq.append(i)
        res = [nums[dq[0]]]

        for i in range(k, numLen):
            while dq and nums[i] >= nums[dq[-1]]:  # 保证一定有nums[dq[i]] > nums[dq[i + 1]]
                dq.pop()
            dq.append(i)
            while dq[0] <= i - k:  # 当前的最大值索引比当前窗口的左边界小，也需要移除
                dq.popleft()
            res.append(nums[dq[0]])
        return res

    def maxSlidingWindow2(self, nums: List[int], k: int) -> List[int]:
        """
        使用堆来存储窗口的数据
        :param nums:
        :param k:
        :return:
        """
        # 方式一：只存数值（超时）
        # numLen = len(nums)
        # tmpWindow = [-nums[i] for i in range(k)]
        # heapq.heapify(tmpWindow)  # 使用堆来存储窗口的元素
        # res = [-tmpWindow[0]]
        # for i in range(k, numLen):
        #     tmpWindow.remove(-nums[i - k])
        #     tmpWindow.append(-nums[i])
        #     heapq.heapify(tmpWindow)
        #     res.append(-tmpWindow[0])
        # return res

        # 方式二：存数值+索引
        numLen, tmpWindow = len(nums), [(-nums[i], i) for i in range(k)]
        heapq.heapify(tmpWindow)
        res = [-tmpWindow[0][0]]
        for i in range(k, numLen):
            heapq.heappush(tmpWindow, (-nums[i], i))
            while tmpWindow[0][1] <= i - k:  # 将索引小于等于当前窗口左边界的元素全部移除
                heapq.heappop(tmpWindow)
            res.append(-tmpWindow[0][0])
        return res

    def maxSlidingWindow1(self, nums: List[int], k: int) -> List[int]:
        """
        暴力法
        :param nums:
        :param k:
        :return:
        """
        numLen = len(nums)
        left, right = 0, k
        tmpWindow = nums[0:k]
        res = []
        while right < numLen:
            res.append(max(tmpWindow))
            del tmpWindow[0]
            tmpWindow.append(nums[right])
            right, left = right + 1, left + 1
        res.append(max(tmpWindow))
        return res

    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        return self.maxSlidingWindow4(nums, k)


if __name__ == "__main__":
    nums, k = [1, 3, -1, -3, 5, 3, 6, 7], 3
    print(Solution().maxSlidingWindow(nums, k))
